package _0

import (
	"sort"
)

/*
时间复杂度：O()
空间复杂度：O()

*/

func minimumCost(cost []int) int {
	sort.Slice(cost, func(i, j int) bool {
		return cost[i] > cost[j]
	})
	ans := 0
	for i := 0; i < len(cost); i += 3 {
		ans += cost[i]
		if i+1 < len(cost) {
			ans += cost[i+1]
		}
	}
	return ans
}

func numberOfArrays(differences []int, lower int, upper int) int {
	minVal, maxVal := 0, 0
	num := 0
	for _, v := range differences {
		num += v
		if num < minVal {
			minVal = num
		}
		if num > maxVal {
			maxVal = num
		}
	}
	sub := maxVal - minVal
	ans := upper - lower - sub + 1
	if ans < 0 {
		return 0
	}
	return ans
}

func numberOfWays(corridor string) int {
	count := 0
	pos := -1
	ans := 0
	for i, ch := range corridor {
		if ch == 'S' {
			count++
			if count%2 == 0 {
				pos = i
			} else {
				if pos != -1 {
					ans += i - pos
				}
			}
		}
	}
	if count == 0 || count%2 != 0 {
		return 0
	}
	if count == 2 {
		return 1
	}
	return ans
}
